//package work.rightAnswer;
//
//
//class numSquare_279 {
//    public int numSquares(int n) {
//        int[] dp = new int[n+1];
//        dp[0] = 1;
//
//        for (int i = 1; i <= n; i++) {
//            int min = Integer.MAX_VALUE;
//            for (int j = 1; j*j <= i; j++) {
//                if(j*j==i){
//                    min = 1;
//                    break;
//                }
//                int num = dp[i-j*j]+dp[j*j];
//                if(num<min){
//                    min = num;
//                }
//            }
//            dp[i] = min;
//        }
//
//        return dp[n];
//    }
//
//    //求得n返回完全平方数的最小数量
//    public int squares(int n){
//        if(isSquare(n)){
//            return 1;
//        }
//
//        int min = Integer.MAX_VALUE;
//        for (int i = 1; i*i < n; i++) {
//            int num = squares(n-i*i)+squares(i*i);
//            if(num<min)min = num;
//        }
//
//        return min;
//
//    }
//
//    private boolean isSquare(int n) {
//        double a = 0;
//        try {
//            a = Math.sqrt(n);
//        } catch (Exception e) {
//            return false;
//        }
//        int b = (int) a;
//        return a - b == 0;
//    }
//
//
//}